package com.lw.leetcode.str.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1147. 段式回文
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/24 20:57
 */
public class LongestDecomposition {


    public static void main(String[] args) {
        LongestDecomposition test = new LongestDecomposition();

        // 7
//        String str = "ghiabcdefhelloadamhelloabcdefghi";

        // 1
//        String str = "merchant";

        // 11
//        String str = "antaprezatepzapreanta";

        // 3
//        String str = "aba";

        // 3
//        String str = "aaa";

        // 3
//        String str = "ababab";

        // 3
        String str = Utils.getStr(1000, 'a', 'c');

        int i = test.longestDecomposition(str);
        System.out.println(i);

    }

    public int longestDecomposition(String text) {
        int length = text.length();
        int m = (length + 1) >> 1;
        int[] arr = new int[m];
        Arrays.fill(arr, 1);
        if ((length & 1) == 0) {
            for (int i = m - 1; i >= 0; i--) {
                if (text.substring(i, m).equals(text.substring(m, length - i))) {
                    arr[i] = 2;
                    break;
                }
            }
        }
        for (int i = m - 2; i >= 0; i--) {
            int j = length - i;
            for (int k = i + 1; k < m; k++) {
                String a = text.substring(i, k);
                String b = text.substring(length - k, j);
                if (a.equals(b)) {
                    arr[i] = Math.max(arr[i], arr[k] + 2);
                }
            }
        }
        return arr[0];
    }

}
